package com.tgy.leetcode;




import java.util.ArrayDeque;
import java.util.Queue;

/**
 * @Author: tgy
 * @Date: 1/7/21 10:27 AM
 */
public class _547_省份数量_BFS {

    public int findCircleNum(int[][] isConnected) {

        if (isConnected == null || isConnected.length == 0 || isConnected[0].length == 0) {

            return 0;
        }

        boolean[] searchs = new boolean[isConnected.length];

        int count = 0;

        Queue<Integer> queue = new ArrayDeque<>();


        for (int i = 0; i < searchs.length; i++) {

            if (!searchs[i]) {
                count++;
                searchs[i] = true;
                queue.offer(i);
                while (!queue.isEmpty()) {

                    int index = queue.poll();

                    for (int j = 0; j < isConnected[index].length; j++) {

                        if (isConnected[index][j] == 1 && !searchs[j]) {

                            searchs[j] = true;
                            queue.offer(j);
                        }
                    }
                }
            }

        }

        return count;
    }




}
